#ifndef _DOUBLELINKLIST_HPP_
#define _DOUBLELINKLIST_HPP_
#include <iostream>
template<typename T>
class DoubleLinkList
{
public:
    DoubleLinkList();
    ~DoubleLinkList();
    void InsertTail(const T& value);
    void InsertHead(const T& value);
    void RemoveHead();
    T& GetHead();
    int Size();
    template<typename U>
    friend std::ostream& operator<<(std::ostream& os,const DoubleLinkList<U>&list);
private:
    struct Node
    {   
        Node(const T& data)
        {
            this->data = data;
            next = prev = nullptr;
        }
        T data;
        Node *next;
        Node *prev;
    };
    Node* GetEnd()
    {
        Node*travelPoint = head;
        while(travelPoint->next != nullptr)
        {
         travelPoint = travelPoint->next;
        }
        return travelPoint;
    }
    Node *head;
    int size;
};
template<typename T>
DoubleLinkList<T>::DoubleLinkList():size(0)
{
    head = new Node(T());
}
template<typename T>
DoubleLinkList<T>::~DoubleLinkList()
{
    while(head != nullptr)
    {
        Node *temp = head->next;
        delete head;
        head = temp;
    }
}
template <typename T>
void DoubleLinkList<T>::InsertTail(const T &value)
{
    Node*newNode = new Node(value);
    Node*end = GetEnd();
    end->next = newNode;
    newNode->prev = end;
    size++;
}

template <typename T>
inline void DoubleLinkList<T>::InsertHead(const T &value)
{
    Node*newNode = new Node(value);
    newNode->next = head->next;
    newNode->prev = head;
    if(head->next)
        head->next->prev = newNode;
    head->next = newNode;
    size++;
}

template <typename T>
inline void DoubleLinkList<T>::RemoveHead()
{
    if(head->next == nullptr)
    return;
    Node *freeNode = head->next;
    head->next = freeNode->next;
    if(freeNode->next)
        freeNode->next->prev = head;
    delete freeNode;
    size--;
}

template <typename T>
inline T &DoubleLinkList<T>::GetHead()
{
    return head->next->data;
}

template <typename T>
inline int DoubleLinkList<T>::Size()
{
    return size;
}

template <typename U>
inline std::ostream &operator<<(std::ostream &os, const DoubleLinkList<U> &list)
{   
    //typename声明后面所跟的参数是一个类型
    typename DoubleLinkList<U>::Node *travelPoint = list.head->next;
    while(travelPoint!=nullptr)
    {
        os<<travelPoint->data<<" ";
        travelPoint = travelPoint->next;
    }
    os<<std::endl;
    return os;
}






#endif